package divide;

/**
 * 最大子线段和
 */
public class MakeSubSum {

    public static int subSum(int[] randomArray) {
        if (randomArray.length == 0) {
            return 0;
        }
        return subSum(randomArray, 0, randomArray.length - 1);
    }

    private static int subSum(int[] array, int L, int R) {
        if (L == R) {
            return Math.max(0, array[L]);
        }
        int M = L + (R - L) / 2;
        int left = subSum(array, L, M);
        int right = subSum(array, M + 1, R);

        int s1 = 0;
        int lefts = 0;
        for (int i = M; i >= L; i--) {
            lefts += array[i];
            if (lefts > s1) {
                s1 = lefts;
            }
        }

        int s2 = 0;
        int rights = 0;
        for (int i = M + 1; i <= R; i++) {
            rights += array[i];
            if (rights > s2) {
                s2 = rights;
            }
        }
        int sum = s1 + s2;
        return Math.max(sum, Math.max(left, right));
    }
}
